//
//$Id: fa.cpp 687 2011-03-13 12:21:29Z andrew.tsyganov $
#include "stdafx.h"

#include "include/fa.h"
#include "include/utils.h"
#include "include/fa_utils.h"
#include "include/sets.h"
#include "include/my_time.h"
#include "contrib/rapidxml/rapidxml.hpp"
#include "contrib/rapidxml/rapidxml_print.hpp"
#include "src/heo/include/sys_api.h"
#include <sstream>
#include <stack>
#include <map>
#include <numeric>
#include <algorithm>

using namespace std;
using namespace rapidxml;

///////////////////////////////////////////////////////////////////////////////
// FA class methods ///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////

// Default constructor
FA::FA() 
{ 
    name_        = "";
    symbols_num_ = 0; 
    states_num_  = 0; 
    epsilon_     = kFADefaultEpsilonName; 

    transitions_num_ = 0;
};

// Manual construction 
FA::FA(string const& name, u_t const symbols_num, u_t const states_num, string const& epsilon) 
{ 
    name_         = name;
    symbols_num_  = symbols_num; 
    states_num_   = states_num; 
    epsilon_      = epsilon; 

    delta_.resize(states_num_);

    transitions_num_ = 0;
};

// Construction from xml file
FA::FA(string const& file) 
{ 
    if (!load_XML(file))
    {
        clear(); 
    }
}

// Construction from rational expression
FA::FA(RE const& re)
{
    REToFA(re, *this);
}

// Copy constructor
FA::FA(FA const& fa)
{
    //clear();

    name_        = fa.name_;
    symbols_num_ = fa.symbols_num_;
    states_num_  = fa.states_num_;
    epsilon_     = fa.epsilon_;
    
    symbols_ = fa.symbols_;
    states_  = fa.states_;

    initial_ = fa.initial_;
    final_   = fa.final_;

    delta_ = fa.delta_;

    transitions_num_ = fa.transitions_num_;
}

// (Re-)initialize already constructed automaton
void FA::init(string const& name, u_t const symbols_num, u_t const states_num, string const& epsilon)
{
    name_         = name;
    symbols_num_  = symbols_num; 
    states_num_   = states_num; 
    epsilon_      = epsilon; 

    symbols_.clear();
    states_.clear();
    initial_.remove();
    final_.remove();
    delta_.clear();

    delta_.resize(states_num_);

    transitions_num_ = 0;
}

// Clear automaton
void FA::clear()
{
    name_        = "";
    symbols_num_ = 0;
    states_num_  = 0;
    epsilon_     = kFADefaultEpsilonName;

    symbols_.clear();
    states_.clear();
    initial_.remove();
    final_.remove();
    delta_.clear();

    transitions_num_ = 0;
}

// Get symbol ID if symbol names are provided 
u_t FA::get_Symbol_ID(Label const& sym) const
{
    if (symbols_.empty())
    {
        cout << "FA::get_Symbol_ID error: symbols vector is empty!" << endl;
        return symbols_num_;
    }

    for (u_t i = 0; i < symbols_.size(); ++i)
    {
        if (symbols_[i] == sym)
        {
            return i;
        }
    }

    cout << "FA::get_Symbol_ID error: symbol not found!" << endl;
    return symbols_num_;
}

// Set symbol names
void FA::set_Symbols(vector<Label> const& vl)
{
    if ((vl.size() > 0) && (vl.size() != symbols_num_))
    {
        cout << "FA::set_Symbols error: wrong vector size!" << endl;
        return;
    }

    symbols_ = vl;
}

// Convert symbol to string representation
string FA::symbol_To_String(u_t const id, string const& pfx, Labels_Type const lt) const
{
    if (id > symbols_num_)
    {
        cout << "FA::symbol_To_String error: symbol id is out of range!" << endl;
        return "";
    }

    if (id < symbols_num_)
    {
        switch (lt)
        {
            case TXT:   return (symbols_.empty() ? MakeLabel(pfx, id, lt) : symbols_[id].to_String());
            case LATEX: return (symbols_.empty() ? MakeLabel(pfx, id, lt) : symbols_[id].to_String());
            case HTML:  return (symbols_.empty() ? MakeLabel(pfx, id, lt) : "<I>" + symbols_[id].to_String() + "</I>"); 
            default:    return (symbols_.empty() ? MakeLabel(pfx, id, lt) : symbols_[id].to_String());
        }
    }
    else
    {
        switch (lt)
        {
            case TXT:   return epsilon_; 
            case LATEX: return "\\" + epsilon_; 
            case HTML:  return "&" + epsilon_ + "\\;"; 
            default:    return epsilon_;
        }
    }
}

// Get state ID if state names are provided 
u_t FA::get_State_ID(Label const& state) const
{
    if (states_.empty())
    {
        cout << "FA::get_State_ID error: states vector is empty!" << endl;
        return states_num_;
    }

    for (u_t i = 0; i < states_.size(); ++i)
    {
        if (states_[i] == state)
        {
            return i;
        }
    }

    cout << "FA::get_State_ID error: state not found!" << endl;
    return states_num_;
}

// Set state names
void FA::set_States(vector<Label> const& vs)
{
    if ((vs.size() > 0) && (vs.size() != states_num_))
    {
        cout << "FA::set_States error: wrong vector size!" << endl;
        return;
    }

    states_ = vs;
}

// Convert state to string representation
string FA::state_To_String(u_t const id, string const& pfx, Labels_Type const lt) const
{
    if (id > states_num_)
    {
        cout << "FA::state_To_String error: state id is out of range!" << endl;
        return "";
    }

    switch (lt)
    {
        case TXT:   return (states_.empty() ? MakeLabel(pfx, id, lt) : states_[id].to_String());
        case LATEX: return (states_.empty() ? MakeLabel(pfx, id, lt) : states_[id].to_String());
        case HTML:  return (states_.empty() ? MakeLabel(pfx, id, lt) : "<I>" + states_[id].to_String() + "</I>"); 
        default:    return (states_.empty() ? MakeLabel(pfx, id, lt) : states_[id].to_String());
    }
}

// Convert subset of states to string representation
string FA::states_To_String(Subset const& s, string const& pfx, Brackets_Type const bt, Labels_Type const lt) const
{
    if (states_.empty())
    {
        return s.to_String(pfx, bt, lt);
    }
    else
    {
        if (s.empty())
        {
            return OpenBracket(bt) + CloseBracket(bt);
        }

        Subset::const_reverse_iterator rit = s.rbegin();

        if (*rit >= states_num_)
        {
            cout << "FA::states_To_String: incorrect set of states!" << endl;
            return "";
        }

        string str = OpenBracket(bt);

        for (Subset::const_iterator it = s.begin(); it != s.end(); ++it)
        {
            str += states_[*it].to_String() + ",";
        }

        str.erase(str.length()-1);
        str += CloseBracket(bt);

        return str;
    }
}

// Add new state
u_t FA::add_State()
{
    if (states_.size() == 0)
    {
        ++states_num_;
        delta_.resize(states_num_);
        return states_num_ - 1; // return state id
    }
    else
    {
        cout << "FA::add_State error: states_ vector is not empty!" << endl;
        return states_num_; // error
    }
}

// Add new states
u_t FA::add_States(u_t n)
{
    if (states_.size() == 0)
    {
        states_num_ += n;
        delta_.resize(states_num_);
        return states_num_ - 1; // return state id
    }
    else
    {
        cout << "FA::add_State error: states_ vector is not empty!" << endl;
        return states_num_; // error
    }
}

// Add new state and provide its name
u_t FA::add_State(Label const& state)
{
    if (states_num_ == states_.size())
    {
        ++states_num_;
        delta_.resize(states_num_);
        states_.push_back(state);
        return states_num_ - 1; // return state id
    }
    else
    {
        cout << "FA::add_State error: states_num and states_.size() must be equal!" << endl;
        return states_num_; // error
    }
}

void FA::swap_States(u_t const id1, u_t const id2)
{
    if ((id1 >= states_num_) || (id2 >= states_num_))
    {
        cout << "FA::swap_States error: state(s) id is out of range!" << endl;
        return;
    }

    bool f1, f2;

    for (u_t i = 0; i < states_num_; ++i)
    {
        for (Adjacent::iterator it = delta_[i].begin(); it != delta_[i].end(); ++it)
        {
            f1 = (*it).second.contains(id1);
            f2 = (*it).second.contains(id2);

            if (f1 && !f2)
            {
                (*it).second.remove(id1);
                (*it).second.insert(id2);
            }
            else
            {
                if (!f1 && f2)
                {
                    (*it).second.remove(id2);
                    (*it).second.insert(id1);
                }
            }
        }
    }

    swap(delta_[id1], delta_[id2]);

    if (!states_.empty())
    {
        swap(states_[id1], states_[id2]);
    }

    f1 = is_Initial(id1);
    f2 = is_Initial(id2);

    if (f1 && !f2)
    {
        initial_.remove(id1);
        initial_.insert(id2);
    }
    else
    {
        if (!f1 && f2)
        {
            initial_.remove(id2);
            initial_.insert(id1);
        }
    }

    f1 = is_Final(id1);
    f2 = is_Final(id2);

    if (f1 && !f2)
    {
        final_.remove(id1);
        final_.insert(id2);
    }
    else
    {
        if (!f1 && f2)
        {
            final_.remove(id2);
            final_.insert(id1);
        }
    }
}

void FA::remove_State(u_t const id)
{
    if (id >= states_num_)
    {
        cout << "FA::remove_State error: state id is out of range!" << endl;
        return;
    }

    if (!states_.empty())
    {
        states_[id].clear();
        for (u_t i = id; i < states_num_ - 1; ++i)
        {
            states_[i] = states_[i + 1];
        }

        states_.resize(states_num_ - 1);
    }

    transitions_num_ -= delta_[id].remove();
    for (u_t i = id; i < states_num_ - 1; ++i)
    {
        delta_[i] = delta_[i + 1];
    }
    --states_num_;
    delta_.resize(states_num_);
    
    for (u_t i = 0; i < states_num_; ++i)
    {
        for (u_t j = 0; j <= symbols_num_; ++j)
        {
            transitions_num_ -= delta_[i].remove(j, id);
        }
    }

    for (u_t i = 0; i < states_num_; ++i)
    {
        for (Adjacent::iterator it_t = delta_[i].begin(); it_t != delta_[i].end(); ++it_t)
        {
            for (Subset::reverse_iterator rit_s = it_t->second.rbegin(); rit_s != it_t->second.rend(); ++rit_s)
            {
                if (*rit_s > id)
                {
                    --const_cast<u_t&>(*rit_s);
                    continue;
                }

                break;
            }
        }
    }

    if (is_Initial(id))
    {
        initial_.remove(id);
    }

    for (Subset::reverse_iterator rit = initial_.rbegin(); rit != initial_.rend(); ++rit)
    {
        if (*rit > id)
        {
            --const_cast<u_t&>(*rit);
            continue;
        }
    }

    if (is_Final(id))
    {
        final_.remove(id);
    }

    for (Subset::reverse_iterator rit = final_.rbegin(); rit != final_.rend(); ++rit)
    {
        if (*rit > id)
        {
            --const_cast<u_t&>(*rit);
            continue;
        }
    }
}

// Set initial state
void FA::set_Initial(u_t const id, bool flag)
{
    if (id >= states_num_)
    {
        cout << "FA::set_Initial error: state id is out of range!" << endl;
        return;
    }

    if (flag)
    {
        initial_.insert(id);
    }
    else
    {
        initial_.remove(id);
    }
}

// Set initial states
void FA::set_Initial(Subset const& s, bool flag)
{
    if (s.empty())
    {
        return;
    }

    Subset::const_reverse_iterator rit = s.rbegin();

    if (*rit >= states_num_)
    {
        cout << "FA::set_Initial error: incorrect set of initial states!" << endl;
        return;
    }

    if (flag)
    {
        for (Subset::const_iterator it = s.begin(); it != s.end(); ++it)
        {
            initial_.insert(*it);
        }
    }
    else
    {
        for (Subset::const_iterator it = s.begin(); it != s.end(); ++it)
        {
            initial_.remove(*it);
        }
    }
}

// Set final state
void FA::set_Final(u_t const id, bool flag)
{
    if (id >= states_num_)
    {
        cout << "FA::set_Final error: state id is out of range!" << endl;
        return;
    }

    if (flag)
    {
        final_.insert(id);
    }
    else
    {
        final_.remove(id);
    }
}

// Set final states
void FA::set_Final(Subset const& s, bool flag)
{
    if (s.empty())
    {
        return;
    }

    Subset::const_reverse_iterator rit = s.rbegin();

    if (*rit >= states_num_)
    {
        cout << "FA::set_Final error: incorrect set of final states!" << endl;
        return;
    }

    if (flag)
    {
        for (Subset::const_iterator it = s.begin(); it != s.end(); ++it)
        {
            final_.insert(*it);
        }
    }
    else
    {
        for (Subset::const_iterator it = s.begin(); it != s.end(); ++it)
        {
            final_.remove(*it);
        }
    }
}

// Add new transition
u_t FA::add_Transition(u_t const src_id, u_t const sym_id, u_t const dst_id)
{
    if (src_id >= states_num_)
    {
        cout << "FA::add_Transition error: source id is out of range!" << endl;
        return 0;
    }

    if (sym_id > symbols_num_)
    {
        cout << "FA::add_Transition error: symbol id is out of range!" << endl;
        return 0;
    }

    if (dst_id >= states_num_)
    {
        cout << "FA::add_Transition error: destination id is out of range!" << endl;
        return 0;
    }

    u_t n = delta_[src_id].insert(sym_id, dst_id);
    transitions_num_ += n;
    
    return n;
}

u_t FA::add_Transitions(u_t const src_id, u_t const sym_id, Subset const& dst_s)
{
    if (dst_s.empty())
    {
        return 0;
    }

    if (*(dst_s.rbegin()) >= states_num_)
    {
        cout << "FA::add_Transitions error: incorrect destination set!" << endl;
        return 0;
    }

    if (src_id >= states_num_)
    {
        cout << "FA::add_Transitions error: source id is out of range!" << endl;
        return 0;
    }

    if (sym_id > symbols_num_)
    {
        cout << "FA::add_Transitions error: symbol id is out of range!" << endl;
        return 0;
    }

    u_t n = delta_[src_id].insert(sym_id, dst_s);
    transitions_num_ += n;
    
    return n;
}

u_t FA::remove_Transition(u_t const src_id, u_t const sym_id, u_t const dst_id)
{
    if (src_id >= states_num_)
    {
        cout << "FA::remove_Transition error: source id is out of range!" << endl;
        return 0;
    }

    if (sym_id > symbols_num_)
    {
        cout << "FA::remove_Transition error: symbol id is out of range!" << endl;
        return 0;
    }

    if (dst_id >= states_num_)
    {
        cout << "FA::remove_Transition error: destination id is out of range!" << endl;
        return 0;
    }

    u_t n = delta_[src_id].remove(sym_id, dst_id);
    transitions_num_ -= n;

    return n;
}

u_t FA::remove_Transition_By_Num(u_t const num)
{
    if (num >= transitions_num_)
    {
        cout << "FA::remove_Transition_By_Num error: num is out of range!" << endl;
        return 0;
    }

    u_t n = 0;
    for (u_t i = 0; i < states_num_; ++i)
    {
        for (Adjacent::iterator it_t = delta_[i].begin(); it_t != delta_[i].end(); ++it_t)
        {
            for (Subset::iterator it_s = it_t->second.begin(); it_s != it_t->second.end(); ++it_s)
            {
                if (n == num)
                {
                    it_t->second.erase(it_s);
                    --transitions_num_;
                    return 1;
                }

                ++n;
            }
        }
    }
    return 0;
}

// Calculate number of transitions outgoing from src_id
u_t FA::calc_Out_Transitions_Num(u_t const src_id) const
{
    if (src_id >= states_num_)
    {
        cout << "FA::calc_Out_Transitions_Num error: source id is out of range!" << endl;
        return 0;
    }

    return delta_[src_id].calc_Out_Transitions_Num();
}

// Calculate number of transitions outgoing from src_id by sym_id
u_t FA::calc_Out_Transitions_Num(u_t const src_id, u_t const sym_id) const
{
    if (src_id >= states_num_)
    {
        cout << "FA::calc_Out_Transitions_Num error: source id is out of range!" << endl;
        return 0;
    }

    if (sym_id > symbols_num_)
    {
        cout << "FA::calc_Out_Transitions_Num error: symbol id is out of range!" << endl;
        return 0;
    }

    return delta_[src_id].calc_Out_Transitions_Num(sym_id);
}

// Calculate number of transitions going to dst_id 
u_t FA::calc_In_Transitions_Num(u_t const dst_id) const
{
    if (dst_id >= states_num_)
    {
        cout << "FA::calc_In_Transitions_Num error: destination id is out of range!" << endl;
        return 0;
    }

    u_t n = 0;
    for (u_t i = 0; i < states_num_; ++i)
    {
        n += delta_[i].calc_In_Transitions_Num(dst_id);
    }

    return n;
}

// Calculate number of transitions going to dst_id by sym_id
u_t FA::calc_In_Transitions_Num(u_t const dst_id, u_t const sym_id) const
{
    if (dst_id >= states_num_)
    {
        cout << "FA::calc_In_Transitions_Num error: destination id is out of range!" << endl;
        return 0;
    }

    if (sym_id > symbols_num_)
    {
        cout << "FA::calc_In_Transitions_Num error: symbol id is out of range!" << endl;
        return 0;
    }

    u_t n = 0;
    for (u_t i = 0; i < states_num_; ++i)
    {
        n += delta_[i].calc_In_Transitions_Num(dst_id, sym_id);
    }

    return n;
}

string FA::transition_To_String(u_t const src_id, u_t const sym_id, u_t const dst_id, Labels_Prefix lp) const
{
    if (src_id >= states_num_)
    {
        cout << "FA::print_Transition error: source id is out of range!" << endl;
        return "";
    }

    if (sym_id > symbols_num_)
    {
        cout << "FA::print_Transition error: symbol id is out of range!" << endl;
        return "";
    }

    if (dst_id >= states_num_)
    {
        cout << "FA::print_Transition error: destination id is out of range!" << endl;
        return "";
    }

    string s;
    //s += StateInOutLabel(is_Initial(src_id), is_Final(src_id), TXT);
    s += " ";
    s += state_To_String(src_id, lp.states_pfx_, TXT);
    s += " -- ";
    s += symbol_To_String(sym_id, lp.symbols_pfx_, TXT);
    s += " --> ";
    s += state_To_String(dst_id, lp.states_pfx_, TXT);
    //s += " ";
    //s += StateInOutLabel(is_Final(dst_id), is_Initial(dst_id), TXT);

    return s;
}

void FA::print_Transitions_TXT(ostream& os, Labels_Prefix lp) const
{
    os << "Transitions of automaton " << get_Name() << endl;

    u_t w = Width(transitions_num_ - 1);
    u_t n = 0;
    for (u_t i = 0; i < states_num_; ++i)
    {
        for (Adjacent::const_iterator it_t = delta_[i].begin(); it_t != delta_[i].end(); ++it_t)
        {
            for (Subset::const_iterator it_s = it_t->second.begin(); it_s != it_t->second.end(); ++it_s)
            {
                os << setw((streamsize) w) << n << ") " << transition_To_String(i, it_t->first, *it_s, lp) << endl;
                ++n;
            }
        }
    }
}

void FA::print_Transitions_TXT(ostream& os, u_t const src_id, Labels_Prefix lp) const
{
    if (src_id >= states_num_)
    {
        cout << "FA::print_Transitions_TXT error: source id is out of range!" << endl;
        return;
    }

    os << "Transitions from state " << state_To_String(src_id, lp.states_pfx_, TXT) << " of automaton " << get_Name() << endl;

    u_t w = Width(calc_Out_Transitions_Num(src_id) - 1);
    u_t n = 0;
    for (Adjacent::const_iterator it_t = delta_[src_id].begin(); it_t != delta_[src_id].end(); ++it_t)
    {
        for (Subset::const_iterator it_s = it_t->second.begin(); it_s != it_t->second.end(); ++it_s)
        {
            os << setw((streamsize) w) << n << ") " << transition_To_String(src_id, it_t->first, *it_s, lp) << endl;
            ++n;
        }
    }
}

void FA::print_Path_TXT(ostream& os, Path const& p, Labels_Prefix lp) const
{
    u_t n = p.size();
    if (n % 2 == 0)
    {
        cout << "FA::print_Path_TXT error: even number of elements in the path!" << endl;
        return;
    }

    cout << state_To_String(p[0], lp.states_pfx_);
    if (n > 1)
    {
        for (u_t i = 1; i <= n-2; i += 2)
        {
            cout << " - " << symbol_To_String(p[i], lp.symbols_pfx_) << " -> "; 
            cout << state_To_String(p[i+1], lp.states_pfx_);
        }
    }
    cout << endl;
}

// Find delta(s, sym_id) (transitions from all states of subset s by symbol sym_id)
Subset FA::move(Subset const& s, u_t const sym_id) const
{
    Subset res;

    for (Subset::const_iterator it_s = s.begin(); it_s != s.end(); ++it_s)
    {
        Adjacent::const_iterator it_t = delta_[*it_s].find(sym_id);
        if (it_t != delta_[*it_s].end())
        {
            res |= it_t->second;
        }
    }

    return res;
}

// Find epsilon closure of subset s
Subset FA::epsilon_Closure(Subset const& s) const
{
    Subset res = s;

    stack<u_t> st;
    
    for (Subset::const_iterator it = s.begin(); it != s.end(); ++it)
    {
        st.push(*it);
    }

    while (!st.empty())
    {
        u_t t = st.top();
        st.pop();

        Adjacent::const_iterator it_t = delta_[t].find(symbols_num_);
        if (it_t != delta_[t].end())
        {
            for (Subset::const_iterator it_s = it_t->second.begin(); it_s != it_t->second.end(); ++it_s)
            {
                if (!res.contains(*it_s))
                {
                    res.insert(*it_s);
                    st.push(*it_s);
                }
            }
        }
    }

    return res;
}

// Check whether sequence of symbols defined by symbol names is acceptable
bool FA::is_Acceptable(std::vector<Label> const& vs) const
{
    vector<u_t> v;

    for (u_t i = 0; i < vs.size(); ++i)
    {
        u_t id = get_Symbol_ID(vs[i]);

        if (id == symbols_num_)
        {
            cout << "FA::is_Acceptable error: symbol not found!" << endl;
            return false;
        }
        else
        {
            v.push_back(id);
        }
    }

    return is_Acceptable(v);
}

// Check whether sequence of symbols defined by symbol IDs is acceptable
bool FA::is_Acceptable(vector<u_t> const& vu) const
{
    Subset s;

    if (is_Epsilon())
    {
        s = epsilon_Closure(initial_);
        
        for (u_t i = 0; i < vu.size(); ++i)
        {
            s = epsilon_Closure(move(s, vu[i]));

            if (s.empty())
            {
                return false;
            }
        }
    }
    else
    {
        s = get_Initial();
        
        for (u_t i = 0; i < vu.size(); ++i)
        {
            s = move(s, vu[i]);

            if (s.empty())
            {
                return false;
            }
        }
    }

    for (Subset::const_iterator it = s.begin(); it != s.end(); ++it)
    {
        if (is_Final(*it))
        {
            return true;
        }
    }

    return false;
}

// Check whether automaton is deterministic
bool FA::is_Deterministic() const
{
    // nondeterministic if it has more than 1 initial state 
    if (initial_.size() > 1)
    {
        return false;
    }

    // nondeterministic if it has epsilon transitions
    if (is_Epsilon())
    {
        return false;
    }

    // nondeterministic if it has more than 1 transition for some symbol
    for (u_t i = 0; i < states_num_; ++i)
    {
        Adjacent::const_iterator it;
        for (Adjacent::const_iterator it = delta_[i].begin(); it != delta_[i].end(); ++it)
        {
            if (it->second.size() > 1)
            {
                return false;
            }
        }
    }

    // deterministic
    return true;
}

// Check whether automaton contains epsilon transitions
bool FA::is_Epsilon() const
{
    for (u_t i = 0; i < states_num_; ++i)
    {
        if (delta_[i].find(symbols_num_) != delta_[i].end())
        {
            return true;
        }
    }

    return false;
}

// Check whether automaton is dense (for each state has at least 1 transition for each symbol)
bool FA::is_Dense() const
{
    if ((symbols_num_ == 0) || (states_num_ == 0))
    {
        return false;
    }

    for (u_t i = 0; i < states_num_; ++i)
    {
        u_t n = delta_[i].size();

        if (n == symbols_num_ + 1)
        {
            continue;
        }

        if (n < symbols_num_)
        {
            return false;
        }

        if (delta_[i].rbegin()->first == symbols_num_)
        {
            return false;
        }
    }

    return true;
}

// make automaton dense (add "dead" state if needed)
void FA::make_Dense(Label const& state)
{
    if (is_Dense())
    {
        return;
    }

    u_t id = (states_num_ == states_.size() ? add_State(state) : add_State());

    for (u_t i = 0; i < states_num_; ++i)
    {
        for (u_t j = 0; j < symbols_num_; ++j)
        {
            if (!delta_[i].contains(j))
            {
                add_Transition(i, j, id);
            }
        }
    }
}

// Convert automaton to GAP's Automata package format
string FA::to_GAP() const
{
    bool eps = is_Epsilon();
    bool det = eps ? false : is_Deterministic();
    u_t    m = eps ? symbols_num_ + 1 : symbols_num_; 

    string s = "Automaton(";

    if (det)
    {
        s += "\"det\", "; 
    }
    else
    {
        s += eps ? "\"epsilon\", " : "\"nondet\", "; 
    }

    s += IntToString(states_num_);
    s += ", ";
    s += IntToString(m);
    s += ", [";

    for (size_t j = 0; j < m; ++j)
    {
        s += "[";

        for (u_t i = 0; i < states_num_; ++i)
        {
            Adjacent::const_iterator it = delta_[i].find(j);
            if (it != delta_[i].end())
            {
                s += det ? it->second.to_String(NO_BRACKETS, 1) : it->second.to_String(BRACKETS, 1);
            }

            if (i < states_num_-1)
            {
                s += ",";
            }
        }

        s += "]";

        if (j < m-1)
        {
            s += ", ";
        }
    }

    s += "], ";
    s += initial_.to_String(BRACKETS, 1);
    s += ", ";
    s += final_.to_String(BRACKETS, 1);
    s += ");";

    return s;
}

// Print automaton in Graphviz format
void FA::print_GV(ostream& os, Labels_Prefix lp) const
{
    string indent = "   ", fake_pfx = "fake_";

    os << "digraph " /*<< name_*/ << endl
       << "{" << endl
       << indent << "layout = dot" << endl
       << indent << "rankdir = LR" << endl
       << indent << "size = 11" << endl
       << endl;

    os << indent << "// states" << endl;
    for (u_t i = 0; i < states_num_; ++i)
    {
        os << indent << i << " [shape = " << (final_.contains(i) ? "doublecircle" : "circle") << ", label = <" 
           << state_To_String(i, lp.states_pfx_, HTML) << ">]" << endl; 
    }
    os << endl;

    os << indent << "// fake states" << endl;
    for (Subset::const_iterator it = initial_.begin(); it != initial_.end(); ++it)
    {
        os << indent << fake_pfx << *it << " [shape = point, color = white]" << endl; 
    }
    os << endl;

    os << indent << "// inputs" << endl;
    for (Subset::const_iterator it = initial_.begin(); it != initial_.end(); ++it)
    {
        os << indent << fake_pfx << *it << " -> " << *it << " [weight = 1000000]" << endl; 
    }
    os << endl;

    if (transitions_num_ > 0)
    {
        os << indent << "// transitions" << endl;
    }

    for (u_t i = 0; i < states_num_; ++i)
    {
        Subset to_states;

        for (Adjacent::const_iterator it = delta_[i].begin(); it != delta_[i].end(); ++it)
        {
            to_states |= it->second;
        }

        //cout << to_states.to_String() << endl;
        
        for (Subset::const_iterator en_states = to_states.begin(); en_states != to_states.end(); ++en_states)
        {
            Subset symbols;

            for (Adjacent::const_iterator it = delta_[i].begin(); it != delta_[i].end(); ++it)
            {
                if (it->second.contains(*en_states))
                {
                    symbols.insert(it->first);
                }
            }
            
            string label; 
            for (Subset::const_iterator en_symbols = symbols.begin(); en_symbols != symbols.end(); ++en_symbols)
            {
                //string symbol = symbol_To_String(*en_symbols, lp.symbols_pfx_, HTML); 
                //label = label + (*en_symbols < symbols_num_ ? symbol : epsilon_) + ",";
                label = label + symbol_To_String(*en_symbols, lp.symbols_pfx_, HTML) + ",";
            }
            label.erase(label.length()-1);
            
            os << indent << i << " -> " << *en_states << " [label = <" << label << ">]" << endl;
        }
        
    }

    os << "}" << endl;
}

// Print automaton in LaTeX format
void FA::print_LaTeX(ostream& os, Labels_Prefix lp) const
{
    bool eps = is_Epsilon();
    bool det = eps ? false : is_Deterministic();
    u_t    m = eps ? symbols_num_ + 1 : symbols_num_; 

    string type;
    
    if (det)
    {
        type = "deterministic";
    }
    else
    {
        if (eps)
        {
            type = "epsilon";
        }
        else
        {
            type = "nondeterministic";
        }
    }

    os << "Automaton " << name_ << " (symbols: " << symbols_num_ << ", states: " << states_num_ << ", transitions: " << transitions_num_ 
       << ", type: "  << type << ")" << endl
       << endl
       << "\\begin{tabular}{lr|";
    for (u_t j = 0; j < m; ++j)
    {
        os << "|c";
    }
    os << "}" << endl;

    os   << " & & ";

    for (u_t j = 0; j < m; ++j)
    {
        os << /*(j < symbols_num_ ? */"$" + symbol_To_String(j, lp.symbols_pfx_, LATEX) + "$"/* : "$\\varepsilon$") */
           << (j < m - 1 ? " & " : " \\\\\n");
    }

    os << "\\hline" << endl
       << "\\hline" << endl;

    for (u_t i = 0; i < states_num_; ++i)
    {
        os << "$" << StateInOutLabel(is_Initial(i), is_Final(i), LATEX) << "$ & $" << state_To_String(i, lp.states_pfx_, LATEX) << "$ & ";

        for (u_t j = 0; j < m; ++j)
        {
            Adjacent::const_iterator it = delta_[i].find(j);
            if (it != delta_[i].end())
            {
                if (!det) 
                {
                    os << "$" << states_To_String(it->second, lp.states_pfx_, LATEX_BRACES, LATEX) << "$"; // \{\} brackets for NFA
                }
                else
                {
                    os << "$" << states_To_String(it->second, lp.states_pfx_, NO_BRACKETS, LATEX) << "$"; // no brackets fo DFA
                }
            }
            else
            {
                os << (!det ? "$\\varnothing$" : "$-$");
            }

            os << (j < m - 1 ? " & " : " \\\\\n");
        }

        os << (i < states_num_ - 1 ? "\\hline\n" : "" );
    }

    os << "\\end{tabular}" << endl;
}

// Print deterministic automaton obtained by subset construction process 
void FA::print_LaTeX(ostream& os, FA const& fa, vector<Subset> const& vs_fa, Labels_Prefix lp_fa, Labels_Prefix lp) const
{
    print_LaTeX(os, lp);

    u_t n = vs_fa.size();

    os << "\\begin{itemize}" << endl;

    for (size_t i = 0; i < n; ++i)
    {
        os << "\\item[" << i << ")] " << "$" << state_To_String(i, lp.states_pfx_, LATEX) << " = " 
           << fa.states_To_String(vs_fa[i], lp_fa.states_pfx_, LATEX_BRACES) << "$" << endl;
    }

    os << "\\end{itemize}" << endl;
}

// Print automaton in text format
void FA::print_TXT(ostream& os, Labels_Prefix lp) const
{
    bool eps = is_Epsilon();
    bool det = eps ? false : is_Deterministic();
    u_t    m = eps ? symbols_num_ + 1 : symbols_num_; 

    string type;
    
    if (det)
    {
        type = "deterministic";
    }
    else
    {
        if (eps)
        {
            type = "epsilon";
        }
        else
        {
            type = "nondeterministic";
        }
    }

    Brackets_Type bt = det ? NO_BRACKETS : BRACES;

    // determine maximum columns width
    u_t max_left_width;
    vector<u_t> max_columns_width(m);

    if (states_.empty())
    {
        max_left_width = state_To_String(states_num_ - 1, lp.states_pfx_).length();
    }
    else
    {
        max_left_width = 0;
        for (u_t i = 0; i < states_num_; ++i)
        {
            u_t len = state_To_String(i).length();
            if (len > max_left_width)
            {
                max_left_width = len;
            }
        }
    }

    for (u_t i = 0; i < symbols_num_; ++i)
    {
        max_columns_width[i] = symbol_To_String(i, lp.symbols_pfx_).length(); 
    }

    if (eps)
    {
        max_columns_width[symbols_num_] = epsilon_.length();
    }

    for (u_t i = 0; i < states_num_; ++i)
    {
        for (u_t j = 0; j < m; ++j)
        {
            Adjacent::const_iterator it = delta_[i].find(j);
            if (it != delta_[i].end())
            {
                u_t len = states_To_String(it->second, lp.states_pfx_, bt).length();
                if (len > max_columns_width[j])
                {
                    max_columns_width[j] = len;
                }
            }
        }
    }

    // determine total table width
    u_t total_width = accumulate(max_columns_width.begin(), max_columns_width.end(), 8 + max_left_width + 3 * m);

    // output name
    os << "Automaton " << name_ << " (symbols: " << symbols_num_ << ", states: " << states_num_ << ", transitions: " << transitions_num_ 
       << ", type: "  << type << ")" << endl;

    // horizontal line
    PrintLine(os, total_width);

    // output table header
    os << "| " << setw((streamsize) max_left_width + 6) << " |";
    for (u_t j = 0; j < symbols_num_; ++j)
    {
        os << setw((streamsize) max_columns_width[j] + 1) << symbol_To_String(j, lp.symbols_pfx_) << " |";
    }
    
    if (eps)
    {
        os << setw((streamsize) max_columns_width[symbols_num_] + 1) << epsilon_ << " |";
    }

    os << endl;

    // horizontal line
    PrintLine(os, total_width);

    // output transition table
    for (u_t i = 0; i < states_num_; ++i)
    {
        os << "| " << StateInOutLabel(is_Initial(i), is_Final(i), TXT) << " "
           << setw((streamsize) max_left_width) << state_To_String(i, lp.states_pfx_) << " |";

        for (u_t j = 0; j < m; ++j)
        {
            os << setw((streamsize) max_columns_width[j] + 1);
            
            Adjacent::const_iterator it = delta_[i].find(j);
            if (it == delta_[i].end())
            {
                os << "" << " |";
            }
            else
            {
                os << states_To_String(it->second, lp.states_pfx_, bt) << " |";
            }
        }
        os << endl;
    }

    // horizontal line
    PrintLine(os, total_width);
}

// Print deterministic automaton obtained by subset construction process 
void FA::print_TXT(std::ostream& os, FA const& fa, vector<Subset> const& vs_fa, Labels_Prefix lp_fa, Labels_Prefix lp) const
{
    print_TXT(os, lp);

    u_t max_width = 0;

    if (states_.empty())
    {
        max_width = state_To_String(states_num_ - 1, lp.states_pfx_).length();
    }
    else
    {
        for (u_t i = 1; i < states_num_; ++i)
        {
            u_t len = state_To_String(i).length();
            if (len > max_width)
            {
                max_width = len;
            }
        }
    }

    for (u_t i = 0; i < states_num_; ++i)
    {
        os << setw((streamsize) max_width) << state_To_String(i, lp.states_pfx_) << " = " << fa.states_To_String(vs_fa[i], lp_fa.states_pfx_) << endl;
    }
}

// Print automaton in xml format (flag - format option for rapidxml)
void FA::print_XML(std::ostream& os, int flag) const
{
    xml_document<> doc;
    xml_node<> *automaton_node;
    xml_node<> *curr_node;
    xml_attribute<> *attr;
    char* buffer;

    // xml version
    curr_node = doc.allocate_node(node_declaration);
    doc.append_node(curr_node);
    
    attr = doc.allocate_attribute(kXmlVersionAttr.c_str(), kXmlVersion.c_str());
    curr_node->append_attribute(attr);

    // application node and its attributes
    curr_node = doc.allocate_node(node_element, kAppXmlNode.c_str(), "");
    doc.append_node(curr_node);

    attr = doc.allocate_attribute(kAppXmlURLAttr.c_str(), kAppURL.c_str());
    curr_node->append_attribute(attr);
    
    attr = doc.allocate_attribute(kAppXmlVersionAttr.c_str(), kAppVersion.c_str());
    curr_node->append_attribute(attr);

    // FA node and its attributes
    automaton_node = doc.allocate_node(node_element, kFAXmlNode.c_str(), "");
    curr_node->append_node(automaton_node);
    
    attr = doc.allocate_attribute(kFAXmlNameAttr.c_str(), name_.c_str());
    automaton_node->append_attribute(attr);

    buffer = doc.allocate_string(IntToString(symbols_num_).c_str());
    attr = doc.allocate_attribute(kFAXmlSymbolsNumAttr.c_str(), buffer);
    automaton_node->append_attribute(attr);
    
    buffer = doc.allocate_string(IntToString(states_num_).c_str());
    attr = doc.allocate_attribute(kFAXmlStatesNumAttr.c_str(), buffer);
    automaton_node->append_attribute(attr);

    // epsilon node
    if (epsilon_ != kFADefaultEpsilonName)
    {
        buffer = doc.allocate_string(epsilon_.c_str());
        curr_node = doc.allocate_node(node_element, kFAXmlEpsilonNode.c_str(), buffer);
        automaton_node->append_node(curr_node);
    }

    // symbols node
    if (!symbols_.empty())
    {
        curr_node = doc.allocate_node(node_element, kFAXmlSymbolsNode.c_str(), "");
        automaton_node->append_node(curr_node);

        for (u_t i = 0; i < symbols_num_; ++i)
        {
            buffer = doc.allocate_string(symbols_[i].to_String().c_str());
            xml_node<>* t = doc.allocate_node(node_element, kFAXmlSymbolNode.c_str(), buffer);
            curr_node->append_node(t);

            buffer = doc.allocate_string(IntToString(i).c_str());
            attr = doc.allocate_attribute(kFAXmlIDAttr.c_str(), buffer);
            t->append_attribute(attr);
        }
    }
    
    // states node
    if (!states_.empty())
    {
        curr_node = doc.allocate_node(node_element, kFAXmlStatesNode.c_str(), "");
        automaton_node->append_node(curr_node);

        for (u_t i = 0; i < states_num_; ++i)
        {
            buffer = doc.allocate_string(states_[i].to_String().c_str());
            xml_node<>* t = doc.allocate_node(node_element, kFAXmlStateNode.c_str(), buffer);
            curr_node->append_node(t);

            buffer = doc.allocate_string(IntToString(i).c_str());
            attr = doc.allocate_attribute(kFAXmlIDAttr.c_str(), buffer);
            t->append_attribute(attr);
        }
    }

    // initial node
    if (!initial_.empty())
    {
        string s = "";
        u_t count = 1;

        for (Subset::const_iterator it = initial_.begin(); it != initial_.end(); ++it)
        {
            s += IntToString(*it);
            if (count < initial_.size())
            {
                s += (count % 20) == 0 ? "\n" : " ";
                ++count;
            }
        }
        
        buffer = doc.allocate_string(s.c_str());
        curr_node = doc.allocate_node(node_element, kFAXmlInitialNode.c_str(), buffer);
        automaton_node->append_node(curr_node);
    }

    // final node
    if (!final_.empty())
    {
        string s = "";
        u_t count = 1;

        for (Subset::const_iterator it = final_.begin(); it != final_.end(); ++it)
        {
            s += IntToString(*it);
            if (count < final_.size())
            {
                s += (count % 20) == 0 ? "\n" : " ";
                ++count;
            }
        }
        
        buffer = doc.allocate_string(s.c_str());
        curr_node = doc.allocate_node(node_element, kFAXmlFinalNode.c_str(), buffer);
        automaton_node->append_node(curr_node);
    }

    // delta node
    if (!delta_.empty())
    {
        curr_node = doc.allocate_node(node_element, kFAXmlDeltaNode.c_str(), "");
        automaton_node->append_node(curr_node);

        for (u_t i = 0; i < states_num_; ++i)
        {
            char* src_buffer = doc.allocate_string(IntToString(i).c_str());

            for (Adjacent::const_iterator it_trans = delta_[i].begin(); it_trans != delta_[i].end(); ++it_trans)
            {
                char* sym_buffer = it_trans->first < symbols_num_ ? doc.allocate_string(IntToString(it_trans->first).c_str()) : NULL;

                for (Subset::const_iterator it_dst = it_trans->second.begin(); it_dst != it_trans->second.end(); ++it_dst)
                {
                    xml_node<>* t = doc.allocate_node(node_element, kFAXmlTransitionNode.c_str(), "");
                    curr_node->append_node(t);

                    attr = doc.allocate_attribute(kFAXmlSrcAttr.c_str(), src_buffer);
                    t->append_attribute(attr);

                    attr = doc.allocate_attribute(kFAXmlSymAttr.c_str(), sym_buffer);
                    t->append_attribute(attr);

                    buffer = doc.allocate_string(IntToString(*it_dst).c_str());
                    attr = doc.allocate_attribute(kFAXmlDstAttr.c_str(), buffer);
                    t->append_attribute(attr);
                }
            }
        }
    }

    rapidxml::print(os, doc, flag);
}

// Save automaton in desired format
bool FA::save(string const& dir, string const& name, string const& format) const
{
    bool save_OK = true;

    if (format == "none")
    {
        return save_OK;
    }
    
    sys_api::Create_Dir_Recursive(dir.c_str());

    if ((format == "gv") || (format == "all"))
    {
        save_OK &= save_GV(CreatePath(dir, name + ".gv"));
    }

    if ((format == "tex") || (format == "all"))
    {
        save_OK &= save_LaTeX(CreatePath(dir, name + ".tex"));
    }

    if ((format == "g") || (format == "all"))
    {
        save_OK &= save_GAP(CreatePath(dir, name + ".g"));
    }

    if ((format == "txt") || (format == "all"))
    {
        save_OK &= save_TXT(CreatePath(dir, name + ".txt"));
    }

    if ((format == "xml") || (format == "all"))
    {
        save_OK &= save_XML(CreatePath(dir, name + ".xml"));
    }

    if (!save_OK)
    {
        cout << "FA::save: output error(s)!";
    }

    return save_OK;
}

// Save automaton in GAP's Automata package format
bool FA::save_GAP(string const& file) const
{
    ofstream ofs;
    ofs.open (file.c_str(), ofstream::out);

    if (ofs.fail())
    {
        cout << "FA::save_GAP: file open error!" << endl;
        return false;
    }

    ofs << "# Automaton: " << name_ << endl;
    ofs << to_GAP();
    
    ofs.close();    

    return true;
}

// Save automaton in Graphviz format
bool FA::save_GV(string const& file) const
{
    ofstream ofs;
    ofs.open (file.c_str(), ofstream::out);

    if (ofs.fail())
    {
        cout << "FA::save_GV: file open error!" << endl;
        return false;
    }

    ofs << "// Automaton: " << name_ << endl
        << endl;

    print_GV(ofs);

    ofs.close();    

    return true;
}

// Save automaton in LaTeX format
bool FA::save_LaTeX(string const& file) const
{
    ofstream ofs;
    ofs.open (file.c_str(), ofstream::out);

    if (ofs.fail())
    {
        cout << "FA::save_LaTeX: file open error!" << endl;
        return false;
    }

    ofs << "\\documentclass[12pt]{article}" << endl
        << "\\usepackage[cp1251]{inputenc}" << endl
        << "\\usepackage{amssymb}" << endl
        << endl
        << "\\begin{document}" << endl
        << endl;

    print_LaTeX(ofs);

    ofs << endl
        << "\\end{document}" << endl;

    ofs.close();    

    return true;
}

// Save automaton in text format
bool FA::save_TXT(string const& file) const
{
    ofstream ofs;
    ofs.open (file.c_str(), ofstream::out);

    if (ofs.fail())
    {
        cout << "FA::save_TXT: file open error!" << endl;
        return false;
    }

    ofs << "Automaton: " << name_ << endl
        << endl;

    print_TXT(ofs);

    ofs.close();    

    return true;
}

// Save automaton in xml format
bool FA::save_XML(string const& file) const
{
    ofstream ofs;
    ofs.open (file.c_str(), ofstream::out);

    if (ofs.fail())
    {
        cout << "FA::save_XML: file open error!" << endl;
        return false;
    }

    print_XML(ofs);

    ofs.close();    

    return true;
}

// Load automaton from xml file
bool FA::load_XML(string const& file)
{
    string name;
    string epsilon;
    u_t symbols_num;
    u_t states_num;

    // process FA node
    vector <char> buffer;
    xml_document<> doc;
    xml_node<>* current_node;
    xml_attribute<>* attribute;
    xml_node<>* automaton_node = GetNode(file, buffer, doc, kFAXmlNode);

    //cout << doc << endl;

    if (automaton_node == NULL)
    {
        cout << "FA::load_XML error: '" << kFAXmlNode << "' node is missing!" << endl;
        return false;
    }

    attribute = automaton_node->first_attribute(kFAXmlNameAttr.c_str(), 0, false);

    if (attribute == NULL)
    {
        cout << "FA::load_XML error: attribute '" << kFAXmlNameAttr << "' of '" << kFAXmlNode << "' node is missing!" << endl;
        return false;
    }

    name = attribute->value();

    attribute = automaton_node->first_attribute(kFAXmlSymbolsNumAttr.c_str(), 0, false);

    if (attribute == NULL)
    {
        cout << "FA::load_XML error: attribute '" << kFAXmlSymbolsNumAttr << "' of '" << kFAXmlNode << "' node is missing!" << endl;
        return false;
    }
    else
    {
        if (atoi(attribute->value()) <= 0)
        {
            cout << "FA::load_XML error: attribute '" << kFAXmlSymbolsNumAttr << "' of '" << kFAXmlNode << "' node is illegal!" << endl;
            return false;
        }
        else
        {
            symbols_num = atoi(attribute->value());
        }
    }

    attribute = automaton_node->first_attribute(kFAXmlStatesNumAttr.c_str(), 0, false);

    if (attribute == NULL)
    {
        cout << "FA::load_XML error: attribute '" << kFAXmlStatesNumAttr << "' of '" << kFAXmlNode << "' node is missing!" << endl;
        return false;
    }
    else
    {
        if (atoi(attribute->value()) <= 0)
        {
            cout << "FA::load_XML error: attribute '" << kFAXmlStatesNumAttr << "' of '" << kFAXmlNode << "' node is illegal!" << endl;
            return false;
        }
        else
        {
            states_num = atoi(attribute->value());
        }
    }

    init(name, symbols_num, states_num);

    // process epsilon node 
    current_node = automaton_node->first_node(kFAXmlEpsilonNode.c_str(), 0, false);

    if (current_node != NULL)
    {
        set_Epsilon(current_node->value());
    }

    // process symbols node
    current_node = automaton_node->first_node(kFAXmlSymbolsNode.c_str(), 0, false);

    if (current_node != NULL)
    {
        vector<Label> vs;
        vs.resize(symbols_num);
        Subset s;
        s.insert_range(0, symbols_num_-1);

        xml_node<>* t = current_node->first_node(kFAXmlSymbolNode.c_str(), 0, false);

        while (t != NULL)
        {
            attribute = t->first_attribute(kFAXmlIDAttr.c_str(), 0, false);

            if (attribute == NULL)
            {
                cout << "FA::load_XML error: attribute '" << kFAXmlIDAttr << "' of '" << kFAXmlSymbolNode << "' node is missing!" << endl;
                return false;
            }
            
            u_t id;

            if ((atoi(attribute->value()) < 0) || ((u_t)atoi(attribute->value()) >= symbols_num_))
            {
                cout << "FA::load_XML error: attribute '" << kFAXmlIDAttr << "' of '" << kFAXmlSymbolNode << "' node is illegal!" << endl;
                return false;
            }
            else
            {
                id = atoi(attribute->value());
            }

            string str = t->value();
            vs[id] = str;
            s.remove(id);
            t = t->next_sibling(kFAXmlSymbolNode.c_str(), 0, false);
        }

        if (!s.empty())
        {
            cout << "FA::load_XML error: one or more '" << kFAXmlSymbolNode << "' nodes are missing!" << endl;
            return false;
        }

        set_Symbols(vs);
    }

    // process states node
    current_node = automaton_node->first_node(kFAXmlStatesNode.c_str(), 0, false);

    if (current_node != NULL)
    {
        vector<Label> vs;
        vs.resize(states_num);
        Subset s;
        s.insert_range(0, states_num_-1);

        xml_node<>* t = current_node->first_node(kFAXmlStateNode.c_str(), 0, false);

        while (t != NULL)
        {
            attribute = t->first_attribute(kFAXmlIDAttr.c_str(), 0, false);

            if (attribute == NULL)
            {
                cout << "FA::load_XML error: attribute '" << kFAXmlIDAttr << "' of '" << kFAXmlStateNode << "' node is missing!" << endl;
                return false;
            }
            
            u_t id;

            if ((atoi(attribute->value()) < 0) || ((u_t)atoi(attribute->value()) >= states_num_))
            {
                cout << "FA::load_XML error: attribute '" << kFAXmlIDAttr << "' of '" << kFAXmlStateNode << "' node is illegal!" << endl;
                return false;
            }
            else
            {
                id = atoi(attribute->value());
            }

            string str = t->value();
            vs[id] = str;
            s.remove(id);
            t = t->next_sibling(kFAXmlStateNode.c_str(), 0, false);
        }

        if (!s.empty())
        {
            cout << "FA::load_XML error: one or more '" << kFAXmlStateNode << "' nodes are missing!" << endl;
            return false;
        }

        set_States(vs);
    }

    // process initial node
    current_node = automaton_node->first_node(kFAXmlInitialNode.c_str(), 0, false);

    if (current_node != NULL)
    {
        string str = current_node->value();
        
        istringstream iss(str);   
        u_t n;
        while (iss >> n) 
        {
            if (n >= states_num_)
            {
                cout << "FA::load_XML error: illegal state id in '" << kFAXmlInitialNode << "' node!" << endl;
            }

            set_Initial(n);
        }
    }

    // process final node
    current_node = automaton_node->first_node(kFAXmlFinalNode.c_str(), 0, false);

    if (current_node != NULL)
    {
        string str = current_node->value();
        
        istringstream iss(str);   
        u_t n;
        while (iss >> n) 
        {
            if (n >= states_num_)
            {
                cout << "FA::load_XML error: illegal state id in '" << kFAXmlFinalNode << "' node!" << endl;
            }

            set_Final(n);
        }
    }

    // process delta node
    current_node = automaton_node->first_node(kFAXmlDeltaNode.c_str(), 0, false);

    if (current_node != NULL)
    {
        xml_node<>* t;

        t = current_node->first_node(kFAXmlTransitionNode.c_str(), 0, false);
        
        while (t != NULL)
        {
            u_t src_id, sym_id, dst_id;

            // process 'src' attribute
            attribute = t->first_attribute(kFAXmlSrcAttr.c_str(), 0, false);
            
            if (attribute == NULL)
            {
                cout << "FA::load_XML error: attribute '" << kFAXmlSrcAttr << "' of '" << kFAXmlTransitionNode << "' node is missing!" << endl;
                return false;
            }
            
            if ((atoi(attribute->value()) < 0) || ((u_t)atoi(attribute->value()) >= states_num_))
            {
                cout << "FA::load_XML error: attribute '" << kFAXmlSrcAttr << "' of '" << kFAXmlTransitionNode << "' node is illegal!" << endl;
                return false;
            }
            else
            {
                src_id = atoi(attribute->value());
            }

            // process 'sym' attribute
            attribute = t->first_attribute(kFAXmlSymAttr.c_str(), 0, false);
            
            if (attribute == NULL)
            {
                cout << "FA::load_XML error: attribute '" << kFAXmlSymAttr << "' of '" << kFAXmlTransitionNode << "' node is missing!" << endl;
                return false;
            }

            if (*(attribute->value()) == 0)
            {
                sym_id = symbols_num_;
            }
            else
            {
                if ((atoi(attribute->value()) < 0) || ((u_t)atoi(attribute->value()) >= symbols_num_))
                {
                    cout << "FA::load_XML error: attribute '" << kFAXmlSymAttr << "' of '" << kFAXmlTransitionNode << "' node is illegal!" << endl;
                    return false;
                }
                else
                {
                    sym_id = atoi(attribute->value());
                }
            }

            // process 'dst' attribute
            attribute = t->first_attribute(kFAXmlDstAttr.c_str(), 0, false);
            
            if (attribute == NULL)
            {
                cout << "FA::load_XML error: attribute '" << kFAXmlDstAttr << "' of '" << kFAXmlTransitionNode << "' node is missing!" << endl;
                return false;
            }
            
            if ((atoi(attribute->value()) < 0) || ((u_t)atoi(attribute->value()) >= states_num_))
            {
                cout << "FA::load_XML error: attribute '" << kFAXmlDstAttr << "' of '" << kFAXmlTransitionNode << "' node is illegal!" << endl;
                return false;
            }
            else
            {
                dst_id = atoi(attribute->value());
            }

            add_Transition(src_id, sym_id, dst_id);

            t = t->next_sibling(kFAXmlTransitionNode.c_str(), 0, false);
        }
    }

    return true;
}

// Serialize automaton
unsigned char* FA::serialize(unsigned& len) const 
{
    // determine buffer size in bytes

    // bytes for name_ 
    len = sizeof(unsigned) + (unsigned) name_.length() * sizeof(char); // bytes for name_ size + 1 byte for each letter

    // bytes for symbols_num_
    len += sizeof(unsigned);

    // bytes for states_num_
    len += sizeof(unsigned);

    // bytes for epsilon_ 
    len += sizeof(unsigned) + (unsigned) epsilon_.length() * sizeof(char); // bytes for epsilon_ size + 1 byte for each letter

    // bytes for symbols_ 
    len += sizeof(unsigned); // number of symbols
    for (u_t i = 0; i < symbols_.size(); ++i)
    {
        len += sizeof(unsigned) + (unsigned) symbols_[i].to_String().length() * sizeof(char); // bytes for i-th name size + 1 byte for each letter
    }

    // bytes for states_ 
    len += sizeof(unsigned); // number of states
    for (u_t i = 0; i < states_.size(); ++i)
    {
        len += sizeof(unsigned) + (unsigned) states_[i].to_String().length() * sizeof(char); // bytes for i-th name size + 1 byte for each letter
    }

    // bytes for initial_ 
    len += sizeof(unsigned) + sizeof(unsigned) * initial_.size(); // size of initial_ + IDs of initial states

    // bytes for final_
    len += sizeof(unsigned) +  sizeof(unsigned) * final_.size(); // size of final_ + IDs of final states

    // bytes for delta_ 
    for (u_t i = 0; i < delta_.size(); ++i)
    {
        len += sizeof(unsigned); // number of delta_[i] elements
        for (Adjacent::const_iterator it = delta_[i].begin(); it != delta_[i].end(); ++it)
        {
            len += 2 * sizeof(unsigned) + sizeof(unsigned) * it->second.size(); // symbol ID + number of destination states + IDs of destination states
        }
    }

    // allocate buffer
    unsigned char* buf = new unsigned char[len];
    unsigned char* t = buf;
    unsigned* p = (unsigned*) buf;

    // write data to buffer

    // write name_
    *p++ = (unsigned) name_.length();
 
    t = (unsigned char*) p;
    for (u_t i = 0; i < name_.length(); ++i)
    {
        *t++ = name_[i];
    }
    p = (unsigned*) t;

    // write symbols_num_
    *p++ = symbols_num_;

    // write states_num_
    *p++ = states_num_;

    // write epsilon_
    *p++ = (unsigned) epsilon_.length();
 
    t = (unsigned char*) p;
    for (u_t i = 0; i < epsilon_.length(); ++i)
    {
        *t++ = epsilon_[i];
    }
    p = (unsigned*) t;

    // write symbols_
    *p++ = (unsigned) symbols_.size();

    for (u_t i = 0; i < symbols_.size(); ++i)
    {
        string str = symbols_[i].to_String();
        u_t n = str.length();
        *p++ = (unsigned) n;
        t = (unsigned char*) p;
        for (u_t j = 0; j < n; ++j)
        {
            *t++ = str[j];
        }
        p = (unsigned*) t;
    }

    // write states_
    *p++ = (unsigned) states_.size();

    for (u_t i = 0; i < states_.size(); ++i)
    {
        string str = states_[i].to_String();
        u_t n = str.length();
        *p++ = (unsigned) n;
        t = (unsigned char*) p;
        for (u_t j = 0; j < n; ++j)
        {
            *t++ = str[j];
        }
        p = (unsigned*) t;
    }

    // write initial_
    *p++ = (unsigned) initial_.size();
    
    for (Subset::const_iterator it = initial_.begin(); it != initial_.end(); ++it)
    {
        *p++ = (unsigned) *it;
    }

    // write final_
    *p++ = (unsigned) final_.size();
    
    for (Subset::const_iterator it = final_.begin(); it != final_.end(); ++it)
    {
        *p++ = (unsigned) *it;
    }

    // write delta_
    for (u_t i = 0; i < delta_.size(); ++i)
    {
        *p++ = (unsigned) delta_[i].size();

        for (Adjacent::const_iterator it_t = delta_[i].begin(); it_t != delta_[i].end(); ++it_t)
        {
            *p++ = (unsigned) it_t->first;
            *p++ = (unsigned) it_t->second.size();
            for (Subset::const_iterator it_s = it_t->second.begin(); it_s != it_t->second.end(); ++it_s)
            {
                *p++ = (unsigned) *it_s;
            }
        }
    }

    // number of bytes written
    //t = (unsigned char *) p;
    //cout << "written = " << (t - (unsigned char*) buf) * sizeof(unsigned char) << endl;

    return buf;
}

// Deserialize automaton
void FA::deserialize(unsigned char const* buf) 
{
    u_t n;

    unsigned char const* t = buf;
    unsigned const* p = (unsigned const*) buf;

    // read name_
    n = (u_t) *p++;
    t = (unsigned char const*) p;
    
    string name((char const*) t, n);

    t += n;
    p = (unsigned const*) t;

    // read symbols_num_
    u_t symbols_num = (u_t) *p++;

    // read states_num_
    u_t states_num = (u_t) *p++;

    // read epsilon_
    n = (u_t) *p++;
    t = (unsigned char const*) p;
    
    string epsilon((char const*) t, n);

    t += n;
    p = (unsigned const*) t;

    // init automaton
    init(name, symbols_num, states_num, epsilon);

    // read symbols_
    n = (u_t) *p++;
    symbols_.resize(n);

    for (u_t i = 0; i < n; ++i) 
    {
        u_t k = (u_t) *p++;
        t = (unsigned char const*) p;

        string s((char const*) t, k);
        symbols_[i] = s;

        t += k;
        p = (unsigned const*) t;
    }

    // read states_
    n = (u_t) *p++;
    states_.resize(n);

    for (u_t i = 0; i < n; ++i) 
    {
        u_t k = (u_t) *p++;
        t = (unsigned char const*) p;

        string s((char const*) t, k);
        states_[i] = s;

        t += k;
        p = (unsigned const*) t;
    }

    // read initial_
    n = (u_t) *p++;

    for (u_t i = 0; i < n; ++i)
    {
        set_Initial((u_t) *p++);
    }

    // read final_
    n = (u_t) *p++;

    for (u_t i = 0; i < n; ++i)
    {
        set_Final((u_t) *p++);
    }

    // read delta_
    for (u_t i = 0; i < states_num; ++i)
    {
        u_t n = (u_t) *p++;

        for (u_t j = 0; j < n; ++j)
        {
            u_t symbol_id = (u_t) *p++;
            u_t k = (u_t) *p++;

            for (u_t l = 0; l < k; ++l)
            {
                add_Transition(i, symbol_id, (u_t) *p++);
            }
        }
    }

    // number of bytes read
    //t = (unsigned char *) p;
    //cout << "read = " << (t - (unsigned char*) buf) * sizeof(unsigned char) << endl;
}

// Find all simple loops in a finite automaton
// output: vsl - vector of all simple loops in fa
void FA::find_Simple_Loops(vector<Simple_Loop>& vsl) const
{
    BitSet visited;
    Path p;

    p.reserve(2 * states_num_ + 1);

    for (u_t i = 0; i < states_num_; ++i)
    { 
        p.push_back(i);
        visited.insert(i);
        find_Simple_Loops_DSF(vsl, p, visited);
        visited.remove(i);
        p.pop_back();
    }
}

void FA::find_Simple_Loops_DSF(vector<Simple_Loop>& vsl, Path& p, BitSet& visited) const
{
    //print_Path_TXT(cout, p);
    u_t k = p.size();
    
    for (Adjacent::const_iterator it_a = delta_[p[k-1]].begin(); it_a != delta_[p[k-1]].end(); ++it_a)
    {
        for (Subset::const_iterator it_s = it_a->second.begin(); it_s != it_a->second.end(); ++it_s)
        {
            if ((*it_s == p[0]) && (k != 1)) // if loop is found
            {
                p.push_back(it_a->first);
                p.push_back(*it_s);
                //print_Path_TXT(cout, p);

                Path c = p;
                MakeCanonicalLoop(c);
                bool found = false;
                for (u_t i = 0; i < vsl.size(); ++i)
                {
                    if (vsl[i] == c)
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                {
                    vsl.push_back(c); // add it if it was not previously encountered
                }

                p.pop_back();
                p.pop_back();
            }
            else //otherwise
            {
                if (!visited.contains(*it_s)) // if state was not visited
                {
                    p.push_back(it_a->first);
                    p.push_back(*it_s);
                    visited.insert(*it_s);
                    find_Simple_Loops_DSF(vsl, p, visited); //search deeper
                    visited.remove(*it_s);
                    p.pop_back();
                    p.pop_back();
                }
            }
        }
    }
}

void MakeCanonicalLoop(Loop& l)
{
    u_t n = l.size();
    
    if (n <= 1)
    {
        return;
    }

    u_t min = l[0], min_pos = 0;
    
    for (u_t i = 2; i <= n-2; i += 2)
    {
        if (l[i] < min)
        {
            min = l[i];
            min_pos = i;
        }
    }

    if (min_pos > 0)
    {
        rotate(l.begin(), l.begin() + min_pos, l.begin() + n - 1);
        l[n-1] = l[0];
    }
}

//EOF!
